HDU 5790 Prefix(字典树、主席树)
题意:
$N\le 10^5个字符串,保证\sum |L_i|\le 10^5,Q\le 10^5次询问$
$在线查询[L, R]区间有多少个不同的前缀$
分析:
$- - 求区间有多少个不同的数的套路$
$考虑离线的做法,询问右端点排序$
$字典树插入每个字符串i,记录每个前缀上次哪里出现$
$然后上次-1,这次+1,对于每个以i为右端点的询问答案就是sum(L, i)$
$这题强制在线,只要可持久化一下就好了$
$时间复杂度O(\sum |L|+qlogn)$
代码:
//
// Created by TaoSama on 2016-08-03
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, q;
char s[N];
int root[N];
struct PersistentSegTree {
static const int M = 1e5 * 40;
int sz;
struct Node {
int ls, rs, sum;
} tree[M];
void init() {
sz = 0;
root[0] = 0;
}
int newNode(int rt) {
tree[++sz] = tree[rt];
return sz;
}
void update(int o, int v, int l, int r, int& rt) {
rt = newNode(rt);
tree[rt].sum += v;
if(l == r) return;
int m = l + r >> 1;
if(o <= m) update(o, v, l, m, tree[rt].ls);
else update(o, v, m + 1, r, tree[rt].rs);
}
int query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) return tree[rt].sum;
int m = l + r >> 1, ret = 0;
if(L <= m) ret += query(L, R, l, m, tree[rt].ls);
if(R > m) ret += query(L, R, m + 1, r, tree[rt].rs);
return ret;
}
} T;
struct Trie {
static const int M = 1e5 + 10, S = 26;
int sz, rt, nxt[M][S];
int val[M];
int newNode() {
val[sz] = 0;
memset(nxt[sz], 0, sizeof nxt[sz]);
return sz++;
}
void init() {
sz = 0;
rt = newNode();
}
void insert(char* s, int id) {
int u = rt;
for(int i = 0; s[i]; ++i) {
int& v = nxt[u][s[i] - 'a'];
if(!v) v = newNode();
if(val[v]) T.update(val[v], -1, 1, n, root[id]);
val[v] = id;
T.update(val[v], 1, 1, n, root[id]);
u = v;
}
}
} trie;
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(scanf("%d", &n) == 1) {
T.init();
trie.init();
for(int i = 1; i <= n; ++i) {
scanf("%s", s);
root[i] = root[i - 1];
trie.insert(s, i);
}
int z = 0;
scanf("%d", &q);
while(q--) {
int l, r; scanf("%d%d", &l, &r);
l = (z + l) % n + 1;
r = (z + r) % n + 1;
if(l > r) swap(l, r);
z = T.query(l, n, 1, n, root[r]);
printf("%d\n", z);
}
}
return 0;
}